package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-03
 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 有 n 个花园，按从1到 n 标记。另有数组 paths ，其中 paths[i] = [xi, yi]描述了花园xi 到花园yi 的双向路径。在每个花园中，你打算种下四种花之一。
 *
 * 另外，所有花园 最多 有 3 条路径可以进入或离开.
 *
 * 你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
 *
 * 以数组形式返回 任一 可行的方案作为答案answer，其中answer[i]为在第(i+1)个花园中种植的花的种类。花的种类用 1、2、3、4 表示。保证存在答案。
 */
public class leetcode1042 {
    public int[] gardenNoAdj(int n, int[][] paths) {
        HashMap<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i,new HashSet<>());
        }
        for (int[] path : paths) {
            int x = path[0]-1, y = path[1]-1;
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            boolean[] used = new boolean[5];
            for (Integer adj : graph.get(i)) {
                //res[adj]表示adj位置上的花的种类(1,2,3,4)
                used[res[adj]] = true;
            }
            //为当前节点选花的种类
            for (int j = 1; j < 5; j++) {
                if (!used[j]) {
                    res[i] = j;
                    break;
                }
            }
        }
        return res;
    }
}
